package com.peng.leetcode.other;

import java.util.ArrayList;
import java.util.List;

/**
 * SpiralOrder
 * 给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。
 *
 * @author: lupeng6
 * @create: 2020/11/28 17:55
 */
public class SpiralOrder {

    public static void main(String[] args) {
        int[][] matrix = new int[3][];
        matrix[0] = new int[]{1, 2, 3, 4};
        matrix[1] = new int[]{5, 6, 7, 8};
        matrix[2] = new int[]{9, 10, 11, 12};
        List<Integer> integers = new Solution().spiralOrder(matrix);
        System.out.println(integers);
    }

    static class Solution {
        public List<Integer> spiralOrder(int[][] matrix) {
            List<Integer> res = new ArrayList<>(matrix.length * matrix[0].length);
            dfs(matrix, 0, matrix[0].length, 0, matrix.length, res);
            return res;
        }

        private void dfs(int[][] matrix, int xStart, int xEnd, int yStart, int yEnd, List<Integer> res) {
            if (xStart >= xEnd || yStart >= yEnd) {
                return;
            }

            int xIndex = xStart;
            while (xIndex < xEnd) {
                res.add(matrix[yStart][xIndex]);
                xIndex++;
            }

            int yIndex = yStart + 1;
            while (yIndex < yEnd) {
                res.add(matrix[yIndex][xEnd-1]);
                yIndex++;
            }

            int bxIndex = xEnd - 2;
            while (bxIndex >= xStart) {
                res.add(matrix[yEnd-1][bxIndex]);
                bxIndex--;
            }

            int lyIndex = yEnd - 2;
            while (lyIndex > yStart) {
                res.add(matrix[lyIndex][yStart]);
                lyIndex--;
            }
            dfs(matrix, xStart + 1, xEnd - 1, yStart + 1, yEnd - 1, res);
        }
    }
}
